{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个无序的整数数组，找到其中最长上升子序列的长度。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: [10,9,2,5,3,7,101,18]\n",
    "输出: 4 \n",
    "解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。\n",
    "说明:\n",
    "\n",
    "可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。\n",
    "你算法的时间复杂度应该为 O(n2) 。\n",
    "进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/longest-increasing-subsequence\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 自己的解体思路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般题目有最长或者最短，可以用动态规划来做。\n",
    "\n",
    "求长度为n的最长上升子序列， 可以求长度为`n-1`的最长子序列，如果n也是上升的话，结果再加1\n",
    "\n",
    "如果是用回溯来的话，回溯的下一层，如果是小于当前的元素就继续向下走，返回条件为数组为空"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "想了一下动态规划还是没啥思路， 先用回溯写吧"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        res = 1\n",
    "        def helper(num_index, start, count):\n",
    "            \"\"\"\n",
    "            num : 上一个数\n",
    "            start: 开始的位置\n",
    "            count: 有多少个\n",
    "            \"\"\"\n",
    "            nonlocal res\n",
    "            for index in range(start, n):\n",
    "                if nums[index] > nums[num_index]:\n",
    "                    res = max(res, count+1)\n",
    "                    helper(index, index+1, count+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            helper(i, i+1, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "居然超时了， 我不服，我用go再写一遍提交"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```golang\n",
    "package main\n",
    "\n",
    "import \"fmt\"\n",
    "\n",
    "func lengthOfLIS(nums []int) int {\n",
    "\tn := len(nums)\n",
    "\tif n <= 1 {\n",
    "\t\treturn n\n",
    "\t}\n",
    "\tres := 1\n",
    "\tvar helper func(int, int, int)\n",
    "\thelper = func(numIndex, start, count int) {\n",
    "\t\tfor i := start; i < n; i++ {\n",
    "\t\t\tif nums[i] > nums[numIndex] {\n",
    "\t\t\t\tres = Max(res, count+1)\n",
    "\t\t\t\thelper(i, i+1, count+1)\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t}\n",
    "\tfor i := 0; i < n; i++ {\n",
    "\t\thelper(i, i+1, 1)\n",
    "\t}\n",
    "\treturn res\n",
    "}\n",
    "func Max(x, y int) int {\n",
    "\tif x < y {\n",
    "\t\treturn y\n",
    "\t}\n",
    "\treturn x\n",
    "}\n",
    "\n",
    "func main() {\n",
    "\ts := lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18})\n",
    "\tfmt.Println(s)\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是超时了。。。\n",
    "\n",
    "看了官方的题解，使用动态规划\n",
    "\n",
    "定义`dp[i]`： `dp[i]`表示i位置的最长上升子序列的值是`dp[i]`\n",
    "\n",
    "状态转移：`dp[i]` 和 `dp[0]`到`dp[i-1]`对比，如果`dp[i]`大于那个数，就记录这个最大数。对比完后，`dp[i]`=那个最大的数+1\n",
    "\n",
    "如果没有找到，`dp[i] = 1`\n",
    "\n",
    "初始化条件，`dp[i] = 1`,因为任何大小的数组，都算是1个最长上升子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "| 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |\n",
    "| -- | - | - | - | - | - | --- | -- |\n",
    "| 1  | 1 | 1 | 2 | 2 | 3 | 4   | 4  |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            m = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    m = max(m, dp[j])\n",
    "            dp[i] = m + 1\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "复杂度 $O(n^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}